package com.leetcode.根据算法进行分类.滑动窗口相关;

import java.util.HashMap;
import java.util.HashSet;

/**
 * @author: ZhouBert
 * @date: 2021/2/9
 * @description:	992. K 个不同整数的子数组
 * https://leetcode-cn.com/problems/subarrays-with-k-different-integers/
 */
public class C_992_K个不同整数的子数组 {

	public static void main(String[] args) {
		C_992_K个不同整数的子数组 action = new C_992_K个不同整数的子数组();
		test1(action);
		test2(action);
	}

	public static void test1(C_992_K个不同整数的子数组 action) {
		//7
		int[] A = new int[]{1, 2, 1, 2, 3};
		int k = 2;
		int res = action.subarraysWithKDistinct(A, k);
		res = action.subarraysWithKDistinctFasterByHashMap(A, k);
		res = action.subarraysWithKDistinctFasterByArray(A, k);
		System.out.println("res = " + res);
	}

	public static void test2(C_992_K个不同整数的子数组 action) {
		//4
		int[] A = new int[]{19, 52, 38, 34, 36, 48, 40, 28, 47, 8, 7, 46, 17, 7, 2, 21, 49, 6, 7, 50, 15, 31, 50, 52, 1, 27, 3, 15, 5, 6, 23, 26, 34, 50, 15, 22, 26, 39, 28, 25, 25, 21, 37, 28, 45};
		int k = 30;
		int res = action.subarraysWithKDistinct(A, k);
		res = action.subarraysWithKDistinctFasterByHashMap(A, k);
		res = action.subarraysWithKDistinctFasterByArray(A, k);
		System.out.println("res = " + res);
	}

	/**
	 * 我能想到的解决方案：
	 * 根据K 的个数，首先使用 sliding windows 确认 K 宽度的个数；
	 * 为了减少遍历次数，再第一次遍历时就确认下该组合里元素集合。
	 * But 这样似乎很麻烦！
	 * --
	 * 于是争取一次遍历完
	 * --
	 * 卧槽，O(n^2) 居然都超时了！-果然是道困难题，只能想着空间换时间来优化了！
	 *
	 * @param A
	 * @param K
	 * @return
	 */
	public int subarraysWithKDistinct(int[] A, int K) {
		int len = A.length;
		int begin = 0, end = 0;
		HashSet<Integer> set = new HashSet<>();
		int res = 0;
		int size = len - K;
		while (end <= size) {
			while (end < len && set.size() < K) {
				set.add(A[end++]);
			}
			if (end == len) {
				if (set.size() == K) {
					res++;
				}
				//此处修复一个BUG
				//由于此时 begin++ 仍然会存在新的 符合条件的连续数组！（连续数组中间存在重复的元素）
				begin++;
				end = begin;
				set.clear();
				continue;
			}
			//此时 [begin -end) 即为最小的一组
			res++;
			while (end < len && set.contains(A[end])) {
				end++;
				res++;
			}

			//此时 end+1 已经是超出的
			begin++;
			end = begin;
			//这里考虑是否可以用空间换时间呢？
			set.clear();
		}
		return res;
	}

	/**
	 * 由于数字存在重复的性质，所以用一个 hashSet 是无法确认集合中是否仍然存在 begin 处的值的！
	 * 所以只能用 hashMap !
	 * 用 hashMap 进行的空间换时间的优化！
	 * 似乎还可以通过 DP 来求解！
	 *
	 * @param A
	 * @param K
	 * @return
	 */
	public int subarraysWithKDistinctFasterByHashMap(int[] A, int K) {
		int len = A.length;
		int begin = 0, end = 0;
		//value - count
		HashMap<Integer, Integer> map = new HashMap<>();
		//map 中 非 0 的数量
		int size = 0;
		int res = 0;
		int lastEnd = 0;
		while (end < len) {
			while (end < len && size < K) {
				if (map.containsKey(A[end])) {
					int v = map.get(A[end]);
					if (v == 0) {
						size++;
					}
					map.put(A[end], v + 1);
				} else {
					map.put(A[end], 1);
					size++;
				}
				end++;
			}

			lastEnd = end;
			if (end == len) {
				if (size == K) {
					res++;
				}
				//此处修复一个BUG
				int num = map.get(A[begin]) - 1;
				if (num == 0) {
					size--;
				}
				map.put(A[begin++], num);
				end = lastEnd;
				continue;
			}
			//此时 [begin -end) 即为最小的一组
			res++;
			//此时不再 对 map 进行维护：因为要从 lastEnd 开始
			while (end < len && (map.containsKey(A[end]) && map.get(A[end]) > 0)) {
				end++;
				res++;
			}

			//此时 end+1 已经是超出的
			int num = map.get(A[begin]) - 1;
			if (num == 0) {
				size--;
			}
			map.put(A[begin++], num);
			end = lastEnd;
		}
		//此时存在 end == len 但是 size == K 的情况
		while (size == K) {
			res++;
			int num = map.get(A[begin++]) - 1;
			if (num == 0) {
				size--;
			}
		}
		return res;
	}

	/**
	 * 由于存在  1 <= A[i] <= A.length 的条件，所以可以用 arr[len + 1] 来替代 hashMap
	 * 以达到节省空间和时间的目的！
	 * 卧槽，用数组比 hashMap 快了近一个数量级！
	 *
	 * @param A
	 * @param K
	 * @return
	 */
	public int subarraysWithKDistinctFasterByArray(int[] A, int K) {
		int len = A.length;
		int begin = 0, end = 0;
		//value
		int[] arr = new int[len + 1];
		//arr 中 非 0 的数量
		int size = 0;
		int res = 0;
		int lastEnd = 0;
		while (end < len) {
			while (end < len && size < K) {
				if (arr[A[end]] == 0) {
					size++;
				}
				arr[A[end]]++;
				end++;
			}

			lastEnd = end;
			if (end == len) {
				if (size == K) {
					res++;
				}
				//此处修复一个BUG
				arr[A[begin]]--;
				if (arr[A[begin++]] == 0) {
					size--;
				}
				end = lastEnd;
				continue;
			}
			//此时 [begin -end) 即为最小的一组
			res++;
			//此时不再 对 map 进行维护：因为要从 lastEnd 开始
			while (end < len && arr[A[end]] > 0) {
				end++;
				res++;
			}

			//此时 end+1 已经是超出的
			arr[A[begin]]--;
			if (arr[A[begin++]] == 0) {
				size--;
			}
			end = lastEnd;
		}
		//此时存在 end == len 但是 size == K 的情况
		while (size == K) {
			res++;
			arr[A[begin]]--;
			if (arr[A[begin++]] == 0) {
				size--;
			}
		}
		return res;
	}

	/**
	 * liweiwei 老师的思路有点 DP 的感觉
	 * 先将问题转为：求解 最多包含 K 个不同整数的子区间的个数
	 * 那么最后的答案就是：最多包含 K 个不同整数的子区间的个数 - 最多包含 K-1 个不同整数的子区间的个数
	 * @param A
	 * @param K
	 * @return
	 */
	public int subarraysWithKDistinctFasterByAmazingMethods(int[] A, int K){
		return atMostKDistinct(A, K) - atMostKDistinct(A, K - 1);
	}

	/**
	 * @param A
	 * @param K
	 * @return 最多包含 K 个不同整数的子区间的个数
	 */
	private int atMostKDistinct(int[] A, int K) {
		int len = A.length;
		int[] freq = new int[len + 1];

		int left = 0;
		int right = 0;
		// [left, right) 里不同整数的个数
		int count = 0;
		int res = 0;
		// [left, right) 包含不同整数的个数小于等于 K
		while (right < len) {
			if (freq[A[right]] == 0) {
				count++;
			}
			freq[A[right]]++;
			right++;

			while (count > K) {
				freq[A[left]]--;
				if (freq[A[left]] == 0) {
					count--;
				}
				left++;
			}
			// [left, right) 区间的长度就是对结果的贡献
			res += right - left;
		}
		return res;
	}
}